/*
 * Double ended queue
 */

#include "Dequeue.h"

#ifndef DEQUEUE_H
#define DEQUEUE_H
const int NMAX = 500000;

struct Dequeue {
	int data[NMAX];
	int head;
	int size;
};
#endif

extern void
Clear(struct Dequeue * d)
{
	d->size = 0;
	d->head = 0;
}



extern int
PushFront(struct Dequeue * d, int key)
{
	if (d->size < NMAX) {
		if (d->head == 0)
			d->head = NMAX-1;
		else
			--d->head;
		d->data[d->head] = key;
		d->size++;
		return 0; /* OK */
	} else {
		return -1; /* deq overflow */
	}
}



extern int
PushBack(struct Dequeue * d, int key)
{
	if (d->size < NMAX) {
		d->data[ (d->head + d->size) % NMAX ] = key;
		++d->size;
		return 0;
	} else {
		return -1; /* deq overflow */
	}
}



extern int
PopFront(struct Dequeue * d)
{
	if (d->size > 0) {
		--d->size;
		return d->data[(d->head)++];
	} else {
		return 0; /* do not touch head and size */
	}
}



extern int
PopBack(struct Dequeue * d)
{
/*	if (d->size) {
		--d->size;
		return d->data[ (d->head + d->size + 1) % NMAX ];
	}
	return 0; */
	return d->size ? d->data[ (d->head + (--d->size)) % NMAX ] : 0;
}



extern int
Front(const struct Dequeue * d)
{
	return d->data[d->head];
}



extern int
Back(const struct Dequeue * d)
{
	return d->data[(d->head + d->size - 1) % NMAX];
}



extern unsigned char
IsEmpty(const struct Dequeue * d)
{
	return d->size ? false : true;
}
